package MAIN;

import java.util.Scanner;
import java.util.StringTokenizer;

//笔试强训第38天
/*选择题*/
/*应用层：针对特定应用规定各层协议，时序，表示等，进行封装，如HTTP
* 表示层：规定数据的格式化表示，数据格式的转换
* 会话层：规定通信时序，数据交换的定界，同步，创建检查点
* 传输层：节点之间可靠的分发数据包
* 网络层：路由（IP寻址），多路访问，寻址
* 数据链路层：检错和纠错，多路访问
* 物理层：定义机械特性，电器特性*/
/*交换机攻击主要有5种类型：1.VLAN跳跃攻击，  2.生成树攻击
* 3.MAC表洪水攻击， 4.ARP攻击  5.VTP攻击
* DHCP攻击：DHCP攻击针对的目标是网络种的DHCP服务器，原理是耗尽DHCP服务器所有的IP地址资源，使其
* 无法正常提供地址分配服务，然后在网络种再假设假冒的DHCP服务器为客户端分发IP地址，从而来实现
* 中间人攻击
* DHCP攻击原理：DHCP没有认证机制，并不知道接收到的报文是否是同一个主机发送的，所以攻击者可以使用
* 以下两种方式来进行攻击：
*  1. 攻击者发送大量而扽DHCP Discover报文，堵塞DHCP服务器处理速度，以至于瘫痪DHCP服务器
*  2. 制造大量的伪造MAC地址来请求地址，导致DHCP服务器中的IP地址耗尽，DHCP也是交换机攻击，
* 一般都是架设在交换机上的*/
/*目录攻击是HTTP所存在的安全漏洞，它使得攻击者能够访问受限的目录，并在Web服务器的根目录意外执行命令
* 不属于交换机攻击*/
public class Main38 {
    //红与黑
    //思路：深度优先遍历：每个节点只遍历一次，并且必须对每个遍历过的节点进行标记（不撞南墙不回头）
    //循环接收每组测试用例然后进行遍历：
    /*1.到达一个新位置：（x，y）看是否是黑色瓷砖
    * 是：遍历--》 标记 + 给走过的黑色瓷砖个数 + 1
    *     还需要继续搜索其他四个方向： 上下左右
    * 否：返回
    * 用递归的方式求解*/

    //定义一个方向数组，等一下在递归遍历上下左右四个方向的时候就加这个数组即可
    static int[][] direct = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int count = 0;
    public static void dfs(char[][] map, int m, int n, int x, int y) {
        //如果该位置已经遍历了或者该位置是白色瓷砖，此时直接返回即可
        if ('#' == map[x][y]) return;
        //这个位置没有遍历 & 是黑色瓷砖
        count++;
        map[x][y] = '#';
        //继续向（x，y）上下左右四个方向进行遍历
        for (int i = 0; i < 4; i++) {
            int nx = x + direct[i][0];
            int ny = y + direct[i][1];

            //需要注意数组越界的情况
            if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                dfs(map, m, n, nx, ny);
            }
        }
    }
    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int m = scan.nextInt();
            int n =scan.nextInt();
            //接收地图的数据并找到起始位置
            char[][] map = new char[m][n];
            int x = 0, y = 0;
            for (int i = 0; i < m; i++) {
                String s = scan.next();//一次性接收一行数据，然后把每个字符放到二维数组中的行中
                for (int j = 0; j < n; j++) {
                    map[i][j] = s.charAt(j);
                    if ('@' == map[i][j]) {
                        x = i;
                        y = j;
                    }
                }
            }
            //按照DFS（深度优先遍历）地图数据，统计黑色瓷砖个数
            boolean[][] flg = new boolean[m][n];
            //注意：此处一定不能使用 Integer 包装类型传参
            // Integer count = 0;
            count = 0;
            dfs(map, m, n, x, y);
            System.out.println(count);
        }
    }

    //蘑菇矩阵
    /*走的规则：如果A处在边界上：最右侧一列或者最底下一行，只能往下走 || 往右走 p = 1.0
    * 其他位置：要么往右走，要么往下走 --- 每次朝某个方向走的概率0.5
    * 动态规划：*/
    public static double sover(int[][] map, int n, int m) {
        double[][] dp = new double[n + 1][m + 1];
        dp[1][1] = 1.0;
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                dp[i][j] = dp[i-1][j] * (j == m ? 1.0 : 0.5) +
                        dp[i][j-1] * (i == n ? 1.0 : 0.5);
                //（i，j）位置可能是蘑菇
                if (map[i][j] == 1) dp[i][j] = 0;
            }
        }
        return dp[n][m];
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();//行
            int m = scan.nextInt();//列
            int k = scan.nextInt();//有多少个蘑菇
            int[][] map = new int[n + 1][m + 1];//多给一行和一列作为初始化
            //然后把蘑菇放入矩阵中(数组中蘑菇置为1)
            while (0 != k) {
                int x = scan.nextInt();
                int y = scan.nextInt();//蘑菇的坐标（x，y）
                map[x][y] = 1;
                k--;
            }
            System.out.printf("%.2f\n", sover(map, n, m));
        }
    }
}
